#include <stdio.h>
#include "global.h"
#include "listDoubleLinked.h"
#include <time.h> //产生随机种子 srand((unsigned int)time(NULL)); //只能精确到秒，所以如果在1秒以内进行取值都是一样的
#include <stdlib.h> //int data = rand();

/**
 * 思路：
 *     双向链表的初始化
 *     双向链表的插入节点
 *     双向链表的删除节点 根据该节点的data值删除，那如果有多个该data值呢？1.根据data删除节点 2.根据要删除的节点pDele删除该节点
 *     双向链表查找
 *     双向链表的销毁
 *     
 *	   对于双向链表，我觉得首尾都可以当头
 *     双向链表排序
 *     合并
 * 
 * */


/*
* 貌似可以不用初始化 0-fail 1-success
* 在debug过程中，发现，*head并不能改变head的指针，也就是退出下面函数后，
* head又变成NULL，但是感觉不对啊,所以如果想在函数体里就改变head指针的值
* 那就得是head指针的指针，才能改变head的地址
* 或者采用返回值的方式记录head的地址也可以
* 下面都是采用返回值的形式
*/
/**
 * 返回值： 头结点
 * */
DOUBLELINKEDLIST* InitDoubleLinkedList(DOUBLELINKEDLIST** head,DoubleLinkedElemType data)
{
	if(*head != NULL) return NULL;
	*head = (DOUBLELINKEDLIST*)malloc(sizeof(DOUBLELINKEDLIST));
    (*head)->m_Data = data;
    (*head)->m_pPre = NULL;
    (*head)->m_pNext = NULL;

	return *head;
}

/**
* 往当前节点后插入,不用返回，因为改变的就是该地址
* 新插入的结点-success NULL-fail
*/
DOUBLELINKEDLIST* InsertNodeToDoubleLinkedList(DOUBLELINKEDLIST** head,DoubleLinkedElemType data)
{
	if(*head == NULL)
	{
		//当前是头结点
		*head = InitDoubleLinkedList(head,data);
		return *head;
	}
	else if((*head)->m_pPre == NULL)
	{
		DOUBLELINKEDLIST* t = *head;
		while(t->m_pNext != NULL)
			t = t->m_pNext;
		t->m_pNext = (DOUBLELINKEDLIST*)malloc(sizeof(DOUBLELINKEDLIST));
		t->m_pNext->m_Data = data;
		t->m_pNext->m_pPre = t;
		//head->m_pNext = t;
		t->m_pNext->m_pNext = NULL;
		return t->m_pNext;
	}
	else
	{
		DOUBLELINKEDLIST* t = *head;
		while(t->m_pPre != NULL)
			t = t->m_pPre;
		t->m_pPre = (DOUBLELINKEDLIST*)malloc(sizeof(DOUBLELINKEDLIST));
		t->m_pPre->m_Data = data;
		t->m_pPre->m_pNext = t;
		//head->m_pNext = t;
		t->m_pPre->m_pPre = NULL;
		return t->m_pPre;
	}

	return NULL;

}

/**
* 删除节点,这个节点唯一的标识符是这个节点的值data，那如果这个data值相等呢？之前的单链表也存在这个问题，
* 这样就不具有普适性了，emm应该就这样
* 0-succ -1-fail
**/
INT16 DelNodeInDoubleLinkedList(DOUBLELINKEDLIST* head,DoubleLinkedElemType data)
{
	if(head == NULL) return -1;
	DOUBLELINKEDLIST* t = head;
	
	while(t != NULL)
	{
		if(t->m_Data == data)
		{
			DOUBLELINKEDLIST* tNext = t->m_pNext;
			t->m_pPre->m_pNext = tNext; //向后 跳过当前节点
			tNext->m_pPre = t->m_pPre; //向前 跳过当前节点
			FREE(t); //释放当前节点
			return 0;
		}
	}
}
/**
* 删除
* 
**/
INT16 DelNodeInDoubleLinkedList2(DOUBLELINKEDLIST* delNode)
{
	if(delNode) return -1;
	DOUBLELINKEDLIST* t = delNode->m_pNext;
	delNode->m_Data = t->m_Data;
	delNode->m_pNext = t->m_pNext;
	delNode->m_pPre = t->m_pNext->m_pPre;
	FREE(t);
	return 0;
}

/**
* 查找结点，懒得写了
**/

/**
* 销毁链表
**/
VOID FreeDoubleLinkedList(DOUBLELINKEDLIST* head)
{
	// NULL <- A <-> B <-> C <-> D <-> E ->NULL 应该和单链表一样，好像记得哪里写过了 
	if(head == NULL) return ;
	DOUBLELINKEDLIST* t = head,*tPre;
	while(t != NULL)
	{
		tPre = t;
		t = t->m_pNext;
		FREE(tPre);
	}
}

/*
* 打印双向链表
*/
VOID PrintDoubleLinkedList(DOUBLELINKEDLIST* head)
{
	if(head->m_pPre == NULL)
	{
		DOUBLELINKEDLIST* t = head; //既然head的指针没有改变，也就不需要临时变量了
		while(t != NULL)
		{
			printf("%p %d\n",t,t->m_Data);
			t = t->m_pNext;
		}
	}
	else if(head->m_pNext == NULL)
	{
		DOUBLELINKEDLIST* t = head;
		while(t != NULL)
		{
			printf("%p %d\n",t,t->m_Data);
			t = t->m_pNext;
		}
	}
}

#ifdef LISTDOUBLELINK_DEBUG
INT16 main(int argc, char const *argv[])
{
	
	INT16 i;
	srand(time(NULL));

	DOUBLELINKEDLIST* head = NULL;
	for(i=0;i<10;i++)
	{
		InsertNodeToDoubleLinkedList(&head,10-i);
	}

    PrintDoubleLinkedList(head);

//	printf("before sort\n");
//	printf("%p\n",head);
//	PrintDoubleLinkedList(head);
//	printf("sorted\n");
//	head = SortDoubleLinkedList(head);
//	PrintDoubleLinkedList(head);

	
	


	return 0;
}
#endif

//****************双向链表 练习题*******************//


/*
* 双向链表排序，链表元素是整型数据
* NULL <- A <-> B <-> C <-> D ->NULL
* 应该也有2种，交换值或者交换地址，或者把值都拿下来再新建一个双向list.直接交换值要比直接交换地址要快？
* succ-1 fail-0
*/

void QuickSortDLList(DOUBLELINKEDLIST* node,DOUBLELINKEDLIST* leftMost,DOUBLELINKEDLIST* rightMost)
{
	if((node == NULL) || (leftMost == rightMost) || (leftMost == NULL) || (rightMost == NULL)) return ;
	int pivot = leftMost->m_Data;
	DOUBLELINKEDLIST* l = leftMost;
	DOUBLELINKEDLIST* r = rightMost;
	while((l != r) && (l != NULL) && (r != NULL) )
	{	
		printf("beyond %p %p\n",l,r);
		while((pivot <= r->m_Data) && (r->m_pPre != NULL) && (l != r))
		{
			r = r->m_pPre;
		}
		//l->m_Data = r->m_Data;
		
		printf("mindle %p %p\n",l,r);
		while((pivot >= l->m_Data) && (l != r) && (l->m_pNext != NULL))
		{
			l = l->m_pNext;
		}
		//r->m_Data = l->m_Data;
		if(l != r)
		SWAP(r->m_Data,l->m_Data);
		printf("below %p %p\n",l,r);

	}
	//跳出while循环后，
	//l->m_Data = pivot;
	leftMost->m_Data = l->m_Data;
	l->m_Data = pivot;
	//！！所以可以在递归调用之前就判断
	if(l != leftMost)
	QuickSortDLList(node,leftMost,l->m_pPre);
	if(l != rightMost)
	QuickSortDLList(node,l->m_pNext,rightMost);

}

DOUBLELINKEDLIST* SortDoubleLinkedList(DOUBLELINKEDLIST* head)
{
	//如果传入的是头
	if(head->m_pPre == NULL)
	{
		DOUBLELINKEDLIST* leftMost = head;
		DOUBLELINKEDLIST* rightMost = head;
		while(rightMost->m_pNext != NULL)
			rightMost = rightMost->m_pNext;
		
		QuickSortDLList(head,leftMost,rightMost);
		return head;
	}
	else if(head->m_pNext == NULL)
	{
		DOUBLELINKEDLIST* rightMost = head;
		DOUBLELINKEDLIST* leftMost = head;
		while(leftMost->m_pPre != NULL)
			leftMost = leftMost->m_pPre;

		QuickSortDLList(head,leftMost,rightMost);
		return head;
	}

	return NULL;
}




